import javax.print.DocFlavor;
import java.io.CharArrayReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode leftNode;
        public TreeNode rightNode;
        public TreeNode(char val){
            this.val=val;
        }
    }
    public TreeNode create(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
        A.leftNode=B;
        A.rightNode=C;
        B.leftNode=D;
        B.rightNode=E;
        C.leftNode=F;
        C.rightNode=G;
        E.rightNode=H;
        return A;
    }
    //检查两棵树是否相同
    public boolean isSameTree(TreeNode root1,TreeNode root2){
        if(root1!=null&&root2==null||root1==null&&root2!=null) {
            return false;
        }
            //根据上述条件判断完毕后，还有可能存在两棵树都为空的情况，或都不为空的情况；
        if(root1==null&&root2==null){
            return true;
        }
        if(root1.val!= root2.val){
            return false;
        }
        return isSameTree(root1.leftNode,root2.leftNode)&&isSameTree(root1.rightNode,root2.rightNode);
    }
     //判断一颗树是否是另⼀棵树的⼦树。
    public boolean isSonTree(TreeNode root,TreeNode rootSon){
        if(root==null){
            return false;
        }
        if(isSameTree(root,rootSon)){
            return true;
        }
        if(isSonTree(root.leftNode,rootSon)){
            return true;
        };
        if(isSonTree(root.rightNode,rootSon)){
            return true;
        }
        return false;
    }
   //翻转⼆叉树
    //方法一：遍历思路；
    public TreeNode fanZhan1(TreeNode root){
        if(root==null){
            return null;
        }
        TreeNode tmp=root.leftNode;
        root.leftNode=root.rightNode;
        root.rightNode=tmp;
        fanZhan1(root.leftNode);
        fanZhan1(root.rightNode);
        return root;
    }
    //方法二：子思路方法；
    public TreeNode fanZhan2(TreeNode root){
        if(root==null){
            return null;
        }
        TreeNode left=fanZhan2(root.leftNode);
        TreeNode right=fanZhan2(root.rightNode);
        if(left==null&&right==null){
            return root;
        }
        root.leftNode=right;
        root.rightNode=left;
        return root;
    }
   //  判断⼀棵⼆叉树是否是平衡⼆叉树。
    //平衡二叉树：根的左右结点的高度差不能大于1；
    //方法一：
    public boolean pingHeng1(TreeNode root){
        if(root==null){
            return true;
        }
        int leftHeight=getHeight1(root.leftNode);
        int rightHeight=getHeight1(root.rightNode);
        if(Math.abs(leftHeight-rightHeight)<=1&&pingHeng1(root.leftNode)&&pingHeng1(root.rightNode)){
            return true;
        }
        return false;
    }
    //获取二叉树的高度；
    public int getHeight1(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHeight=getHeight1(root.leftNode);
        int rightHeight=getHeight1(root.rightNode);
        return Math.max(leftHeight,rightHeight)+1;
    }
    //方法二：
    public boolean pingHeng2(TreeNode root){
        if(root==null){
            return true;
        }
        return getHeight2(root)>=0;
    }
    //获取二叉树的高度；
    //方法二：
    public int getHeight2(TreeNode root){
        if(root==null){
            return 0;
        }
        int legtHeight=getHeight2(root.leftNode);
        if(legtHeight<0){
            return -1;
        }
        int rightHeight=getHeight2(root.rightNode);
        if(rightHeight<0){
            return -1;
        }
        if(Math.abs(legtHeight-rightHeight)<=1){
            return Math.max(legtHeight,rightHeight)+1;
        }else{
            return -1;
        }
    }

 //判断一棵树是否是对称⼆叉树；
    public boolean duiCheng(TreeNode root){
        if(root==null){
            return true;
        }
        return duiChengSon(root.leftNode,root.rightNode);
    }
    public boolean duiChengSon(TreeNode l,TreeNode r){
        if(l!=null&&r==null||l==null&&r!=null){
            return false;
        }
        if(l==null&&r==null){
            return true;
        }
        if(l.val!=r.val){
            return false;
        }
        return duiChengSon(l.leftNode,r.rightNode)&&duiChengSon(l.rightNode,r.leftNode);
    }
   //  ⼆叉树的构建及遍历。
    public void createTree(String str){
        TreeNode  root=createTreeSon(str);
        middleOrder(root);
    }
    //中序遍历；
    public void middleOrder(TreeNode root){
        if(root==null){
            return;
        }
        middleOrder(root.leftNode);
        System.out.print(root.val+" ");
        middleOrder(root.leftNode);
    }
    //二叉树的创建；
    public static int i=0;
    public TreeNode createTreeSon(String str){
        TreeNode root=null;
        char ch=str.charAt(i);
        if(ch!='#'){
             root=new TreeNode(ch);
            i++;
            root.leftNode=createTreeSon(str);
            root.rightNode=createTreeSon(str);
        }else{
            i++;
        }
        return root ;
    }
    //. ⼆叉树的分层遍历(层序遍历);
    //方法一：
    public void order1(TreeNode root){
        if(root==null){
            return;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode ret=queue.poll();
            System.out.print(ret.val+" ");
            if(ret.leftNode!=null){
                queue.offer(ret.leftNode);
            }
            if(ret.rightNode!=null){
                queue.offer(ret.rightNode);
            }
        }
    }
    //方法二：
    public List<List<Character>> order2(TreeNode root){
        List<List<Character>> ret=new ArrayList<>();
        if(root==null){
            return null;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Character> list1=new ArrayList<>();
            int size= queue.size();
            while(size!=0){
                TreeNode cur=queue.poll();
                list1.add(cur.val);
                if(cur.leftNode!=null){
                    queue.offer(root.leftNode);
                }
                if(cur.rightNode!=null){
                    queue.offer(root.rightNode);
                }
            }
            ret.add(list1);
        }
        return ret;
    }

//前序遍历：
    //方法一：
    List<Character> list=new ArrayList<>();
    public List<Character> preOrder(TreeNode root){
        if(root==null){
            return null;
        }
        list.add(root.val);
        preOrder(root.leftNode);
        preOrder(root.rightNode);
        return list;
    }

    //方法二：
    public List<Character> preOrder2(TreeNode root){
        if(root==null){
            return null;
        }
        List<Character> list=new ArrayList<>();
        list.add(root.val);
        List<Character> left=preOrder2(root.leftNode);
        list.addAll(left);
        List<Character> right=preOrder2(root.rightNode);
        list.addAll(right);;
        return list;
    }

}
